package day_2022_7_to_8.day48;

/**
 * @author haomin
 * @date 2022/08/19 18:50
 **/
public class Day34_5_Num79_Exist {
    class Solution {
        public boolean exist(char[][] board, String word) {
            for(int i = 0;i < board.length;++i){
                for(int j = 0;j < board[0].length;++j){
                    if(board[i][j] == word.charAt(0)){
                        if(findWord(board, word, i , j, 0)) return true;
                    }
                }
            }
            return false;
        }
        private boolean findWord (char[][] board, String word, int i, int j, int k){
            if(k >= word.length()) return true;
            if(i < 0 || i > board.length-1 || j < 0 || j > board[0].length-1 ||
                    board[i][j] != word.charAt(k)) return false;

            board[i][j]+=58;
            boolean res = findWord(board,word,i-1,j,k+1) || findWord(board,word,i+1,j,k+1) ||
                    findWord(board,word,i,j-1,k+1) || findWord(board,word,i,j+1,k+1);
            board[i][j]-=58;
            return res;
        }
    }
}